import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉搜索树的最近公共祖先
 * User: wangxin
 * Date: 2024-11-11
 * Time: 22:58
 */


   class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

public class test {
    public ArrayList<Integer> getPath(TreeNode root,int t){
        ArrayList<Integer> path = new ArrayList<>();
        TreeNode node = root;
        while(node.val !=t){
            path.add(node.val);
            if(t < node.val){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        ArrayList<Integer> path_p = getPath(root,p);
        ArrayList<Integer> path_q = getPath(root,q);
        int res = 0;
        for(int i = 0;i<path_p.size()&&i<path_q.size();i++){
            int x = path_p.get(i);
            int y = path_q.get(i);
            if(x==y){
                res = path_p.get(i);
            }else{
                break;
            }
        }
        return res;
    }
}
